#include <iostream>
using namespace std;
int vs[1001],w[1001],dp[1001];
int main()
{
  int v,n;cin>>v>>n;
  for(int i=0;i<n;i++)
    cin>>vs[i]>>w[i];
    cout<<"i\tvs[i]\tw[i]\tj\tdp[j]\tdp[x]\t1\t2\t3\t4\t5\t6\t7\t8"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=v;j>=vs[i];j--){
            cout<<i<<"\t"<<vs[i]<<'\t'<<w[i]<<'\t'<<j<<"\t"<<dp[j]<<"\t"<<dp[j-vs[i]]+w[i]<<"\t";
            dp[j]=max(dp[j],dp[j-vs[i]]+w[i]);
            for(int k=1;k<=v;k++)
              cout<<dp[k]<<"\t";
            cout<<endl;
        }
    }
    for(int i=1;i<=v;i++)
        cout<<i<<" "<<dp[i]<<endl;
  return 0;
}